#include "types.h"
#include "defs.h"
#include "param.h"
#include "memlayout.h"
#include "mmu.h"
#include "x86.h"
#include "proc.h"
#include "spinlock.h"
#include "fs.h"
#include "fcntl.h"
#include "file.h"

struct {
  struct spinlock lock;
  struct proc proc[NPROC];
} ptable;

// A pid is a 32-bit number, 4 bytes. We append ".swp" to the end of the file, another 4 bytes. Final byte for '\0'
#define SWP_NAME_SIZE 9
#define SWAP_THRESHOLD 1
#define MAX_SWAP_RUNS 10
static struct proc *initproc;
// Process that swaps out memory of sleeping processes
static struct proc *swapperProc = 0;

// Signals whether there are processes that need to be swapped back in
static int needSwapIn = 0;

int nextpid = 1;
extern void forkret(void);
extern void trapret(void);

static void wakeup1(void *chan);

void
pinit(void)
{
  initlock(&ptable.lock, "ptable");
  ENABLE_SWAPPING = 0;
}

//PAGEBREAK: 32
// Look in the process table for an UNUSED proc.
// If found, change state to EMBRYO and initialize
// state required to run in the kernel.
// Otherwise return 0.
static struct proc*
allocproc(void)
{
  struct proc *p;
  char *sp;

  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    if(p->state == UNUSED)
      goto found;
  release(&ptable.lock);
  return 0;

found:
  p->state = EMBRYO;
  p->pid = nextpid++;
  release(&ptable.lock);

  // Allocate kernel stack.
  if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;
  
  // Leave room for trap frame.
  sp -= sizeof *p->tf;
  p->tf = (struct trapframe*)sp;
  
  // Set up new context to start executing at forkret,
  // which returns to trapret.
  sp -= 4;
  *(uint*)sp = (uint)trapret;

  sp -= sizeof *p->context;
  p->context = (struct context*)sp;
  memset(p->context, 0, sizeof *p->context);
  p->context->eip = (uint)forkret;
	p->internal = 0;
	p->swapping = 0;
	//p->enableSwapping = 0;

  return p;
}

static void
fileSwapName (uint pid, char* out, const int outSize)
{
	uint cpid = pid;
	int len, i;
	char temp;

	// poor man's itoa for unsigned integers
	for (len = 0; ((len < outSize-1) && (cpid > 0)); len++)
	{
		out[len]  = (cpid % 10) + 48; //48 is ascii of zero
		cpid = cpid / 10;
	}

	// Reverse it so it's the proper number
	for (i=0; i < (len / 2); i++)
	{
		temp = out[i];
		out[i] = out[len-(i+1)];
		out[len - (i+1)] = temp;
	}
	// See if we have room to do more than end the string
	if ((outSize - len) >= 6)
	{
		out[len++] = '.';
		out[len++] = 's';
		out[len++] = 'w';
		out[len++] = 'p';
	}
	out[len++]  = '\0';
}
void 
swapIn(void)
{
	// Still holding ptable lock from scheduler
	release(&ptable.lock);
	struct proc *pToSwap, *p;
	for (;;)
	{
		acquire(&ptable.lock);
		pToSwap = 0;
		for (p = ptable.proc; p < &ptable.proc[NPROC] && needSwapIn; p++)
		{
			if (RUNNABLE_SUSPENDED == p->state)
			{
				pToSwap = p;
				break;
			}
		}
		if (!pToSwap)
		{
			// No point running if there's nothing that needs swapping
			needSwapIn = 0;
			release(&ptable.lock);
			yield();
		}
		else
		{
			release(&ptable.lock);
			char pname[SWP_NAME_SIZE];
			fileSwapName(pToSwap->pid, pname, SWP_NAME_SIZE);
			
			struct file *swpFile = kernelOpen(pname, O_RDONLY);	
			
			if (!swpFile)
			{
				panic("Failed to open swap file for process");
			}
			uint oldsz = 0;
			
			int bRead = fileread(swpFile, (char*) &oldsz, sizeof(uint));
			
			if (bRead < 0)
			{
				panic("Failed to read old heap size from swap file");
			}
			// Re-allocating memory for the process
			bRead = allocuvm(pToSwap->pgdir, pToSwap->sz, oldsz);
			if (0 == bRead)
			{
				// Maybe this should just give up instead? Panic may be unwarranted, it's just this process that can't run
				panic("Could not allocate memory to swap process in");
			}
			
			
			// Now that the process has memory backing it's address space again, we tell loaduvm to read the rest of the swap file into memory
			bRead = loaduvm(pToSwap->pgdir, 0, swpFile->ip, sizeof(uint), oldsz);
			
			
			fileclose(swpFile);
			
			if (bRead < 0)
			{
				panic("Failed to swap in process memory");
			}
			
			unlink(pname);
			
			// If we made it this far, the process has successfully had it's memory swapped in
			acquire(&ptable.lock);
			
			
			pToSwap->sz = oldsz;
			pToSwap->state = RUNNABLE;
			needSwapIn = (needSwapIn > 0) ? needSwapIn - 1 : 0;
			release(&ptable.lock);
		}
	}
}
// Sets up an "internal" process - one that executes in kernel mode instead of user mode. Entrypoint function should NOT return, as this will currently cause it
// to exceed kstack boundaries, resulting in undefined behavior
static struct proc*
createInternalProcess(const char *name, void (*entrypoint)())
{
		struct proc *p = 0;
		p = allocproc();
		if (p)
		{
			p->internal = 1;
			// By doing this, we make sure that the process will never return to trapret, which would cause it to cross rings into user space
			/*
			char *sp = (char*) p->context;
			sp +=sizeof(*p->context);
			*(uint*) sp =  (uint) entrypoint;*/
			p->context->eip = (uint) entrypoint;
			// Setting current working directory to root
  		p->cwd = namei("/");
			// Copying process name
  		safestrcpy(p->name, name, sizeof(p->name));
			p->state = RUNNABLE;
			// We specifically don't setup a pgdir, since this process will be kept in kernel mode

		}
		return p;
}

void
createSwapProcess(void)
{
	if (!swapperProc)
	{
		swapperProc = createInternalProcess("Inswapper", swapIn);
	}
}
//PAGEBREAK: 32
// Set up first user process.
void
userinit(void)
{
  struct proc *p;
  extern char _binary_initcode_start[], _binary_initcode_size[];
  
  p = allocproc();
  initproc = p;
  if((p->pgdir = setupkvm(kalloc)) == 0)
    panic("userinit: out of memory?");
  inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
  p->sz = PGSIZE;
  memset(p->tf, 0, sizeof(*p->tf));
  p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
  p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
  p->tf->es = p->tf->ds;
  p->tf->ss = p->tf->ds;
  p->tf->eflags = FL_IF;
  p->tf->esp = PGSIZE;
  p->tf->eip = 0;  // beginning of initcode.S

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  p->state = RUNNABLE;
}

// Grow current process's memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;
  sz = proc->sz;
  if(n > 0){
    if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  } else if(n < 0){
    if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  }
  proc->sz = sz;
  switchuvm(proc);
  return 0;
}

// Create a new process copying p as the parent.
// Sets up stack to return as if from system call.
// Caller must set state of returned proc to RUNNABLE.
int
fork(void)
{
  int i, pid;
  struct proc *np;

  // Allocate process.
  if((np = allocproc()) == 0)
    return -1;

  // Copy process state from p.
  if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){
    cprintf("problem coping uvm\n");
    kfree(np->kstack);
    np->kstack = 0;
    np->state = UNUSED;
    return -1;
  }
  np->sz = proc->sz;
  np->parent = proc;
  *np->tf = *proc->tf;

  // Clear %eax so that fork returns 0 in the child.
  np->tf->eax = 0;

  for(i = 0; i < NOFILE; i++)
    if(proc->ofile[i])
      np->ofile[i] = filedup(proc->ofile[i]);
  np->cwd = idup(proc->cwd);
 
  pid = np->pid;
  np->state = RUNNABLE;
  safestrcpy(np->name, proc->name, sizeof(proc->name));
  //np->enableSwapping = proc->enableSwapping;
  return pid;
}

// Exit the current process.  Does not return.
// An exited process remains in the zombie state
// until its parent calls wait() to find out it exited.
void
exit(void)
{
  struct proc *p;
  int fd;

  if(proc == initproc)
    panic("init exiting");

  // Close all open files.
  for(fd = 0; fd < NOFILE; fd++){
    if(proc->ofile[fd]){
      fileclose(proc->ofile[fd]);
      proc->ofile[fd] = 0;
    }
  }

  iput(proc->cwd);
  proc->cwd = 0;

  acquire(&ptable.lock);

  // Parent might be sleeping in wait().
  wakeup1(proc->parent);

  // Pass abandoned children to init.
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->parent == proc){
      p->parent = initproc;
      if(p->state == ZOMBIE)
        wakeup1(initproc);
    }
  }

  // Jump into the scheduler, never to return.
  proc->state = ZOMBIE;
  sched();
  panic("zombie exit");
}

// Wait for a child process to exit and return its pid.
// Return -1 if this process has no children.
int
wait(void)
{
  struct proc *p;
  int havekids, pid;

  acquire(&ptable.lock);
  for(;;){
    // Scan through table looking for zombie children.
    havekids = 0;
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->parent != proc)
        continue;
      havekids = 1;
      if(p->state == ZOMBIE){
        // Found one.
        pid = p->pid;
        kfree(p->kstack);
        p->kstack = 0;
        freevm(p->pgdir);
        p->state = UNUSED;
        p->pid = 0;
        p->parent = 0;
        p->name[0] = 0;
        p->killed = 0;
	p->swapping = 0;
        release(&ptable.lock);
        return pid;
      }
    }

    // No point waiting if we don't have any children.
    if(!havekids || proc->killed){
			cprintf("C %d K %d\n", havekids, proc->killed);
      release(&ptable.lock);
      return -1;
    }

    // Wait for children to exit.  (See wakeup1 call in proc_exit.)
    sleep(proc, &ptable.lock);  //DOC: wait-sleep
  }
}

void
register_handler(sighandler_t sighandler)
{
  char* addr = uva2ka(proc->pgdir, (char*)proc->tf->esp);
  if ((proc->tf->esp & 0xFFF) == 0)
    panic("esp_offset == 0");

    /* open a new frame */
  *(int*)(addr + ((proc->tf->esp - 4) & 0xFFF))
          = proc->tf->eip;
  proc->tf->esp -= 4;

    /* update eip */
  proc->tf->eip = (uint)sighandler;
}


void
swapOut(void)
{
	char pname[SWP_NAME_SIZE];
	fileSwapName(proc->pid, pname, SWP_NAME_SIZE);

	struct file *swpFile = kernelOpen(pname, O_CREATE | O_WRONLY);	
	if (swpFile)
	{
		int i, succ, bToWrite, oldsz;
		succ = 0;
		oldsz = proc->sz;
		bToWrite = sizeof(uint);
		// See below for explanation 
		succ = filewrite(swpFile, (char*) &oldsz, bToWrite);
		succ = (succ == bToWrite);
		for (i = 0;  i < oldsz && succ; i += PGSIZE)
		{
						/* Not sure if we want to release ptable or enable interrupts. Basic idea, though, is that we've 
							 changed both the IDE disk driver and the inode functions to use busy wait in place of sleep.
							 This means they HAVE to be interruptible, otherwise the write will never finish (IDE sends
							 an interrupt to tell us when an operation is done). For the moment, we release the spinlock,
							 which makes a form of sense, but I'm unsure if there isn't anything dangerous about letting someone
							 else potentially touch the process table at this time.

							 Example - what if someone else touches the process while we're waiting on the IDE's interrupt? But then,
							 if they're trying to acquire ptable's lock, it doesn't help to keep holding it, as that would just make the 
							 handler get stuck there. Need to do something about this, maybe remove p from the ptable until we're done here,
							 then put it back.
						*/
						bToWrite  =  (((oldsz - i) < PGSIZE) ? oldsz - i : PGSIZE);
						// We want to write the entire user address space, even if the page isn't user accessible (though not if the page isn't present - that's bad).
						char* addToWrite = uva2kaOp(proc->pgdir, (char*) i, 1, 0);
						succ = filewrite(swpFile, addToWrite, bToWrite);
						succ = (succ == bToWrite);
		}
		fileclose(swpFile);
		
		if (succ)
		{
			// If we managed to write everything, then we can suspend the process and free it's memory
			proc->sz = deallocuvm(proc->pgdir, oldsz, 0);
			if (proc->state == RUNNABLE_SWAPPING)
			{
				proc->state = RUNNABLE_SUSPENDED;
			}
			else
			{
				proc->state = SLEEPING_SUSPENDED;
			}
		}
		else
		{
			panic("Write to swap file failed");
		}
	}
	else
	{
		panic("Could not open file for swap");
	}
}

// Relies on holding the ptable lock
static void trySwap()
{  
	int canSwap = (logBusy() == 0);
	/*
		If the log is busy right now, we can't swap out proc - forcing our way into the log's lock is insanely dangerous and stupid. Most processes
		can just wait for their turn at it, but we can't, since we're not really a process.
		If the log isn't busy, however, then it never will be. No kernel code writes to a file unless it's a kernel panic, in which case we're screwed anyway.

		So we are justified in using the logBusy check as an absolute indicator of whether a swap is possible at the moment.
	*/
	if (canSwap)
	{
		cprintf("Swapping %d\n", proc->pid);
		proc->swapping = 1;
		release(&ptable.lock);
		swapOut();
		acquire(&ptable.lock);
		proc->swapping = 0;
	}
	else
	{
		cprintf("Not swapping %d\n", proc->pid);
	}
}
//PAGEBREAK: 42
// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns.  It loops, doing:
//  - choose a process to run
//  - swtch to start running that process
//  - eventually that process transfers control
//      via swtch back to the scheduler.
void
scheduler(void)
{
  struct proc *p;
	int skipSwapper = 0;
	int swapperRuns = 0;
  for(;;){
    // Enable interrupts on this processor.
    sti();

    // Loop over process table looking for process to run.
    acquire(&ptable.lock);

		// If we skipped the swapper last time, we won't now
		if (skipSwapper)
		{
			skipSwapper = 0;
		}
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
			if ((needSwapIn >= SWAP_THRESHOLD) && (!skipSwapper))
			{
				// Past a certain point of processes waiting, the swapper proc gets priority
				p = swapperProc;
			}
			if ((SLEEPING == p->state) && (ENABLE_SWAPPING!=0))
			{
				// A sleeping process is one that we couldn't swap out earlier. We try again now.
				proc = p;
				trySwap();
				continue;
			}
      if(p->state != RUNNABLE)
        continue;
			// Making sure the swapper proc doesn't get CPU time until we actually need it to
			if ((p == swapperProc) && !needSwapIn)
				continue;

			// Reset the counter of contiguous swap runs
			if (p != swapperProc)
			{
				swapperRuns = 0;
			}
      // Switch to chosen process.  It is the process's job
      // to release ptable.lock and then reacquire it
      // before jumping back to us.
      proc = p;
			// Internal processes use the kernel's page table
			if (!(proc->internal))
			{
      	switchuvm(p);
			}
      p->state = RUNNING;
      swtch(&cpu->scheduler, proc->context);

			// Internal processes use the kernel's page table
			if (!(proc->internal))
			{
      	switchkvm();
			}

			// If we just finished running the swapper, we update the counter of contiguous swapper runs
			if (proc == swapperProc)
			{
				swapperRuns++;
				// Prevent deadlock by stopping the swapper from running too many times in a row
				if (swapperRuns >= MAX_SWAP_RUNS)
				{
					skipSwapper = 1;
					swapperRuns = 0;
				}
			}
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      proc = 0;
    }
    release(&ptable.lock);

  }
}

// Enter scheduler.  Must hold only ptable.lock
// and have changed proc->state.
void
sched(void)
{
  int intena;

  if(!holding(&ptable.lock))
    panic("sched ptable.lock");
  if(cpu->ncli != 1)
    panic("sched locks");
  if(proc->state == RUNNING)
    panic("sched running");
  if(readeflags()&FL_IF)
    panic("sched interruptible");
  intena = cpu->intena;
  swtch(&proc->context, cpu->scheduler);
  cpu->intena = intena;
}

// Give up the CPU for one scheduling round.
void
yield(void)
{
  acquire(&ptable.lock);  //DOC: yieldlock
  proc->state = RUNNABLE;
  sched();
  release(&ptable.lock);
}

// A fork child's very first scheduling by scheduler()
// will swtch here.  "Return" to user space.
void
forkret(void)
{
  static int first = 1;
  // Still holding ptable.lock from scheduler.
  release(&ptable.lock);

  if (first) {
    // Some initialization functions must be run in the context
    // of a regular process (e.g., they call sleep), and thus cannot 
    // be run from main().
    first = 0;
    initlog();
  }
  // Return to "caller", actually trapret (see allocproc).
}

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void
sleep(void *chan, struct spinlock *lk)
{
  if(proc == 0)
    panic("sleep");

  if(lk == 0)
    panic("sleep without lk");

	if (proc->state == SLEEPING)
	{
		panic("Double sleep");
	}
  // Must acquire ptable.lock in order to
  // change p->state and then call sched.
  // Once we hold ptable.lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup runs with ptable.lock locked),
  // so it's okay to release lk.
  if(lk != &ptable.lock){  //DOC: sleeplock0
    acquire(&ptable.lock);  //DOC: sleeplock1
    release(lk);
  }

  // Go to sleep.
  proc->chan = chan;
  proc->state = SLEEPING;
  if (ENABLE_SWAPPING)
	trySwap();
  sched();

  // Tidy up.
  proc->chan = 0;

  // Reacquire original lock.
  if(lk != &ptable.lock){  //DOC: sleeplock2
    release(&ptable.lock);
    acquire(lk);
  }
}

//PAGEBREAK!
// Wake up all processes sleeping on chan.
// The ptable lock must be held.
static void 
wakeup1(void *chan)
{
  struct proc *p;
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
	{
		if (chan == p->chan)
		{
			if (SLEEPING_SUSPENDED == p->state)
			{
      	p->state = RUNNABLE_SUSPENDED;
				needSwapIn++;
			}
			// If we're here, the process is assuredly NOT in the process of being swapped out, so it's safe
			// to mark it as runnable.
			if (SLEEPING == p->state)
			{
				// If the process is being swapped out during this wakeup, then we move it to an intermediate state to tell swapOut to 
				// move it to RUNNABLE_SUSPENDED when it's done
				if (p->swapping)
				{
					p->state = RUNNABLE_SWAPPING;
				}
				else
				{
					p->state = RUNNABLE;
				}
			}
		}
	}
}

// Wake up all processes sleeping on chan.
void
wakeup(void *chan)
{
  	acquire(&ptable.lock);
  	wakeup1(chan);
  	release(&ptable.lock);
}

// Kill the process with the given pid.
// Process won't exit until it returns
// to user space (see trap in trap.c).
int
kill(int pid)
{
  struct proc *p;

	cprintf("KILL\n");
  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->pid == pid){
      p->killed = 1;
      // Wake process from sleep if necessary.
      if(p->state == SLEEPING_SUSPENDED)
			{
        p->state = RUNNABLE_SUSPENDED;
				needSwapIn++;
			}
			if (p->state == SLEEPING)
			{
				p->state = RUNNABLE;
			}
      release(&ptable.lock);
      return 0;
    }
  }
  release(&ptable.lock);
  return -1;
}

//PAGEBREAK: 36
// Print a process listing to console.  For debugging.
// Runs when user types ^P on console.
// No lock to avoid wedging a stuck machine further.
void
procdump(void)
{
  static char *states[] = {
  [UNUSED]    "unused",
  [EMBRYO]    "embryo",
  [SLEEPING]  "sleep ",
	[SLEEPING_SUSPENDED] "ssleep",
	[RUNNABLE_SUSPENDED] "srunble",
  [RUNNABLE]  "runble",
  [RUNNING]   "run   ",
  [ZOMBIE]    "zombie"
  };
  int i;
  struct proc *p;
  char *state;
  uint pc[10];
  
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->state == UNUSED)
      continue;
    if(p->state >= 0 && p->state < NELEM(states) && states[p->state])
      state = states[p->state];
    else
      state = "???";
    cprintf("%d %s %s", p->pid, state, p->name);
    if((p->state == SLEEPING) || (p->state == SLEEPING_SUSPENDED)){
      getcallerpcs((uint*)p->context->ebp+2, pc);
      for(i=0; i<10 && pc[i] != 0; i++)
        cprintf(" %p", pc[i]);
    }
    cprintf("\n");
  }
}
